<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Ecological Bin Packing</title>
<meta name="description" content="Ecological Bin Packing">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00102_archivos/htmlatex.css">
<script type="text/javascript" src="acm-00102_archivos/jsapi"></script><script src="acm-00102_archivos/a" type="text/javascript"></script><script src="acm-00102_archivos/defaultes.js" type="text/javascript"></script></head><body lang="EN" bgcolor="#ffffff">
 <h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font size="5" color="#c0ffff">&nbsp;<a name="SECTION0001000000000000000000">Ecological Bin Packing</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Background</a></font></h2>
<p>
Bin packing, or the placement of objects of certain weights into
different bins subject to certain constraints, is an historically
interesting problem.  Some bin packing problems are NP-complete but are
amenable to dynamic programming solutions or to approximately optimal
heuristic solutions.
</p><p>
In this problem you will be solving a bin packing problem that deals
with recycling glass.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">The Problem</a></font></h2>
<p>
Recycling glass requires that the glass be separated by color into one
of three categories: brown glass, green glass, and clear glass.  In this
problem you will be given three recycling bins, each containing a
specified number of brown, green and clear bottles.  In order to be
recycled, the bottles will need to be moved so that each bin contains
bottles of only one color.
</p><p>
The problem is to minimize the number of bottles that are moved.  You
may assume that the only problem is to minimize the number of movements
between boxes.
</p><p>
For the purposes of this problem, each bin has infinite
capacity and the only constraint is moving the bottles so that each
bin contains bottles of a single color. The total number of bottles will never exceed 2^31.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">The Input</a></font></h2>
<p>
The input consists of a series of lines with each line containing 9
integers.  The first three integers on a line represent the number of
brown, green, and clear bottles (respectively) in bin number 1, the
second three represent the number of brown, green and clear bottles
(respectively) in bin number 2, and the last three integers
represent the number of brown, green, and clear bottles
(respectively)
in bin number 3.  For example, the line
10 15 20 30 12 8 15 8 31
</p><p>
indicates that there are 20 clear bottles in bin 1, 12 green bottles in
bin 2, and 15 brown bottles in bin 3.
</p><p>
Integers on a line will be separated by one or more spaces.  Your
program should process all lines in the input file.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">The Output</a></font></h2>
<p>
For each line of input there will be one line of output indicating what color
bottles go in what bin to minimize the number of bottle movements.
You should also print the minimum number of bottle movements.
</p><p>
The output should consist of a string of the
three upper case characters 'G', 'B',
'C' (representing the colors green, brown, and clear) representing the
color associated with each bin.
</p><p>
The first character of the string
represents
the color associated with the first bin, the second character of the
string represents the color associated with the second bin, and the
third character represents the color associated with the third bin.
</p><p>
The integer indicating the minimum number of bottle movements
should follow the string.
</p><p>
If more than one order of brown, green, and clear bins
yields the minimum number of movements
then the alphabetically first string representing a minimal
configuration should be printed.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001005000000000000000">Sample Input</a></font></h2>
<p>
</p><pre>1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10</pre>
<h2><font color="#0070e8"><a name="SECTION0001006000000000000000">Sample Output</a></font></h2>
<p>
</p><pre>BCG 30
CBG 50</pre>
<p>
</p><div style="border-style: solid; border-color: rgb(38, 108, 111); border-width: 1px 2.5px 2px 0.5px; padding: 1pt 3pt; position: absolute; display: none; z-index: 1000; background-color: rgb(236, 231, 197); font-size: 10pt; font-family: sans-serif; color: rgb(1, 1, 34);"></div></body></html>